{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Tree Diameter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: treeDiameter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #树的直径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你这棵「无向树」，请你测算并返回它的「直径」：这棵树上最长简单路径的 <strong>边数</strong>。</p>\n",
    "\n",
    "<p>我们用一个由所有「边」组成的数组 <code>edges</code>&nbsp;来表示一棵无向树，其中&nbsp;<code>edges[i] = [u, v]</code>&nbsp;表示节点&nbsp;<code>u</code> 和 <code>v</code>&nbsp;之间的双向边。</p>\n",
    "\n",
    "<p>树上的节点都已经用&nbsp;<code>{0, 1, ..., edges.length}</code>&nbsp;中的数做了标记，每个节点上的标记都是独一无二的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/31/1397_example_1.png\" style=\"height: 233px; width: 226px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>edges = [[0,1],[0,2]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "这棵树上最长的路径是 1 - 0 - 2，边数为 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/31/1397_example_2.png\" style=\"height: 316px; width: 350px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释： </strong>\n",
    "这棵树上最长的路径是 3 - 2 - 1 - 4 - 5，边数为 4。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= edges.length &lt;&nbsp;10^4</code></li>\n",
    "\t<li><code>edges[i][0] != edges[i][1]</code></li>\n",
    "\t<li><code>0 &lt;= edges[i][j] &lt;= edges.length</code></li>\n",
    "\t<li><code>edges</code>&nbsp;会形成一棵无向树</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [tree-diameter](https://leetcode.cn/problems/tree-diameter/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [tree-diameter](https://leetcode.cn/problems/tree-diameter/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[0,2]]', '[[0,1],[1,2],[2,3],[1,4],[4,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        edges.sort(key = lambda x:x[0])\n",
    "        ans = 0\n",
    "        dic = {}\n",
    "        for x in edges:\n",
    "            if x[0] not in dic:\n",
    "                dic[x[0]] = [x[1]]\n",
    "            else:\n",
    "                dic[x[0]].append(x[1])\n",
    "        ans = 0\n",
    "        def dfs(i:int):\n",
    "            pre_len = 0\n",
    "            if i not in dic: return 0\n",
    "            nonlocal ans\n",
    "            for cur in dic[i]:\n",
    "                cur_len = dfs(cur)+1\n",
    "                ans = max(ans,cur_len+pre_len)\n",
    "                pre_len = max(cur_len,pre_len)\n",
    "            return pre_len\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeDiameter:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_diameter_bfs(edge):\n",
    "\n",
    "        def bfs(node):\n",
    "            # 模板：使用BFS计算获取树的直径端点以及直径长度\n",
    "            d = 0\n",
    "            q = deque([(node, -1, d)])\n",
    "            while q:\n",
    "                node, pre, d = q.popleft()\n",
    "                for nex in edge[node]:\n",
    "                    if nex != pre:\n",
    "                        q.append((nex, node, d + 1))\n",
    "            return node, d\n",
    "\n",
    "        n = len(edge)\n",
    "\n",
    "        # 这个算法依赖于一个性质，对于树中的任一个点，距离它最远的点一定是树上一条直径的一个端点\n",
    "        x, _ = bfs(0)\n",
    "        # 任取树中的一个节点x，找出距离它最远的点y，那么点y就是这棵树中一条直径的一个端点。我们再从y出发，找出距离y最远的点就找到了一条直径\n",
    "        y, dis = bfs(x)\n",
    "        return dis\n",
    "    \n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "        return TreeDiameter().get_diameter_bfs(dct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if not edges:   return 0\n",
    "        nodeDict = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            nodeDict[x].append(y)\n",
    "            nodeDict[y].append(x)\n",
    "\n",
    "        visited = [0] * len(nodeDict)\n",
    "        def bfs(start, flag):\n",
    "            stack = [start]\n",
    "            d = 0\n",
    "            visited[start] += 1\n",
    "            while stack:\n",
    "                temp = []\n",
    "                for cur in stack:\n",
    "                    for nex in nodeDict[cur]:\n",
    "                        if visited[nex] == flag:\n",
    "                            temp.append(nex)\n",
    "                            visited[nex] += 1\n",
    "                if not temp:\n",
    "                    return d, stack[0]\n",
    "                else:\n",
    "                    stack = temp\n",
    "                    d += 1\n",
    "\n",
    "        _, nex = bfs(0, 0)\n",
    "        d, _ = bfs(nex, 1)\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        st = [0 for _ in range(n)]\n",
    "        pq = deque()\n",
    "        pq.append(0)\n",
    "        st[0] = 1\n",
    "        lv = 0 # last_ver\n",
    "        while pq:\n",
    "            t = pq.popleft()\n",
    "            lv = t\n",
    "            for ver in g[t]:\n",
    "                if st[ver] == 0:\n",
    "                    pq.append(ver)\n",
    "                    st[ver] = 1\n",
    "        st = [0 for _ in range(n)]\n",
    "        pq = deque()\n",
    "        pq.append((lv,0))\n",
    "        st[lv] = 1\n",
    "        ml = 0\n",
    "        while pq:\n",
    "            t, dis = pq.popleft()\n",
    "            ml = max(ml, dis)\n",
    "            for ver in g[t]:\n",
    "                if st[ver] == 0:\n",
    "                    pq.append((ver, dis + 1))\n",
    "                    st[ver] = 1\n",
    "        return ml            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n=len(edges)\n",
    "        ad=collections.defaultdict(list)\n",
    "        for s,e in edges:\n",
    "\n",
    "            ad[s].append(e)\n",
    "            ad[e].append(s)\n",
    "        stack=collections.deque()\n",
    "        stack.append(0)\n",
    "        vis=[False]*(n+1)\n",
    "        while stack:\n",
    "            cur=stack.popleft()\n",
    "            if vis[cur]==True:\n",
    "                continue\n",
    "            vis[cur]=True\n",
    "            for nex in ad[cur]:\n",
    "                if vis[nex]==False:\n",
    "                    stack.append(nex)\n",
    "        top=cur\n",
    "        vis=[False]*(n+1)\n",
    "\n",
    "        level=0\n",
    "\n",
    "        stack=collections.deque()\n",
    "        nexstack=collections.deque()\n",
    "        stack.append(top)\n",
    "        while stack:\n",
    "            cur=stack.pop()\n",
    "            if vis[cur]==True:\n",
    "                continue\n",
    "            vis[cur]=True\n",
    "            for nex in ad[cur]:\n",
    "                if vis[nex]==False:\n",
    "                    nexstack.append(nex)\n",
    "            if not stack and nexstack:\n",
    "                level+=1\n",
    "                stack=nexstack\n",
    "                nexstack=collections.deque()\n",
    "\n",
    "\n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if not edges:   return 0\n",
    "        nodeDict = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            nodeDict[x].append(y)\n",
    "            nodeDict[y].append(x)\n",
    "\n",
    "        visited = [0] * len(nodeDict)\n",
    "        def bfs(start, flag):\n",
    "            stack = [start]\n",
    "            d = 0\n",
    "            visited[start] += 1\n",
    "            while stack:\n",
    "                temp = []\n",
    "                for cur in stack:\n",
    "                    for nex in nodeDict[cur]:\n",
    "                        if visited[nex] == flag:\n",
    "                            temp.append(nex)\n",
    "                            visited[nex] += 1\n",
    "                if not temp:\n",
    "                    return d, stack[0]\n",
    "                else:\n",
    "                    stack = temp\n",
    "                    d += 1\n",
    "\n",
    "        _, nex = bfs(0, 0)\n",
    "        d, _ = bfs(nex, 1)\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n=len(edges)\n",
    "        g=[[] for _ in range(n+1)]\n",
    "        for edge in edges:\n",
    "            g[edge[0]].append(edge[1])\n",
    "            g[edge[1]].append(edge[0])\n",
    "        parents=[-1 for i in range(n+1)]\n",
    "        def bfs(idx):\n",
    "            vis=[False for i in range(n+1)]\n",
    "            dq=deque()\n",
    "            vis[idx]=True\n",
    "            dq.append(idx)\n",
    "            while dq:\n",
    "                x=dq.popleft()\n",
    "                for y in g[x]:\n",
    "                    if vis[y] is False:\n",
    "                        vis[y]=True\n",
    "                        parents[y]=x\n",
    "                        dq.append(y)\n",
    "            return x\n",
    "\n",
    "        x=bfs(0)\n",
    "        y=bfs(x)\n",
    "        cnt=0\n",
    "        while y!=x:\n",
    "            y=parents[y]\n",
    "            cnt+=1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        n = len(edges)+1\n",
    "\n",
    "        def bfs(start):\n",
    "            visited = [False]*n\n",
    "            queue = [start]\n",
    "\n",
    "            height = -1\n",
    "            while queue:\n",
    "                len_q = len(queue)\n",
    "                for i in range(len_q):\n",
    "                    x=queue.pop(0)\n",
    "                    visited[x] = True\n",
    "                    for nei in graph[x]:\n",
    "                        if not visited[nei]:\n",
    "                            queue.append((nei))\n",
    "                height += 1\n",
    "            \n",
    "            return x, height\n",
    "        \n",
    "        x, _ = bfs(0)\n",
    "        # print(x,_)\n",
    "        _, height = bfs(x)\n",
    "        # print(_,height)\n",
    "\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1  # 树的结点个数n = 边数len(edegs) + 1 \n",
    "        # 创建二叉树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(n-1):  # edges[i][0]是edges[i][1]的父节点，g[i]是i的孩子结点\n",
    "            g[edges[i][0]].append(edges[i][1])\n",
    "\n",
    "        ans = 0  \n",
    "        def dfs(x):  # 返回当前以x为根节点的树的各子树中的最长链长\n",
    "            nonlocal ans\n",
    "            x_len = 0  # 初始化最长链长为0\n",
    "\n",
    "            for y in g[x]:  # 遍历x的子树\n",
    "                y_len = dfs(y) + 1\n",
    "                ans = max(ans, x_len + y_len)  # 更新并维护ans = 最长 + 次长\n",
    "                x_len = max(x_len, y_len)  # 不断更新x子树中的最长链\n",
    "            return x_len \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1  # 获取树的结点个数n = 边数 + 1 \n",
    "        # 创建二叉树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(n-1):\n",
    "            g[edges[i][0]].append(edges[i][1])\n",
    "        ans = 0\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            x_len = 0\n",
    "            for y in g[x]:\n",
    "                y_len = dfs(y) + 1\n",
    "                ans = max(ans, x_len + y_len)\n",
    "                x_len = max(x_len, y_len)\n",
    "            return x_len\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        di = defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            di[i].append(j)\n",
    "            di[j].append(i)\n",
    "        \n",
    "        def dfs(u, fa, di):\n",
    "            nonlocal ans\n",
    "            max1, max2 = 0, 0\n",
    "            for v in di[u]:\n",
    "                if v != fa:\n",
    "                    t = dfs(v, u, di) + 1\n",
    "                    if max1 < t:\n",
    "                        max2 = max1\n",
    "                        max1 = t\n",
    "                    elif max2 < t:\n",
    "                        max2 = t\n",
    "            ans = max(ans, max1 + max2)\n",
    "            return max1\n",
    "        ans = 0\n",
    "        dfs(0, -1, di)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        graph = collections.defaultdict(list)\n",
    "        degree = [0] * n\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "            degree[edge[0]] += 1\n",
    "            degree[edge[1]] += 1\n",
    "        q = [u for u in range(n) if degree[u] == 1]\n",
    "        left_node = n\n",
    "        res = 0\n",
    "        while left_node > 1:\n",
    "            level = len(q)\n",
    "            for _ in range(level):\n",
    "                u = q.pop(0)\n",
    "                for v in graph[u]:\n",
    "                    degree[v] -= 1\n",
    "                    if degree[v] == 1:\n",
    "                        q.append(v)\n",
    "            res += 2\n",
    "            left_node -= level\n",
    "        if left_node == 0:\n",
    "            res -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if not edges: return 0\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        q = deque([edges[0][0]])\n",
    "        vis = set()\n",
    "        vis.add(edges[0][0])\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for _ in range(n):\n",
    "                cur = q.popleft()\n",
    "                for nxt in g[cur]:\n",
    "                    if nxt not in vis:\n",
    "                        vis.add(nxt)\n",
    "                        q.append(nxt)\n",
    "        \n",
    "        vis.clear()\n",
    "        q = deque()\n",
    "        q.append(cur)\n",
    "        vis.add(cur)\n",
    "        ans = -1\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            ans += 1\n",
    "            for _ in range(n):\n",
    "                cur = q.popleft()\n",
    "                for nxt in g[cur]:\n",
    "                    if nxt not in vis:\n",
    "                        vis.add(nxt)\n",
    "                        q.append(nxt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        graph = collections.defaultdict(list)\n",
    "        degree = [0] * n\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "            degree[edge[0]] += 1\n",
    "            degree[edge[1]] += 1\n",
    "        q = [u for u in range(n) if degree[u] == 1]\n",
    "        left_node = n\n",
    "        res = 0\n",
    "        while left_node > 1:\n",
    "            level = len(q)\n",
    "            for _ in range(level):\n",
    "                u = q.pop(0)\n",
    "                for v in graph[u]:\n",
    "                    degree[v] -= 1\n",
    "                    if degree[v] == 1:\n",
    "                        q.append(v)\n",
    "            res += 2\n",
    "            left_node -= level\n",
    "        if left_node == 0:\n",
    "            res -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        adjVex = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            adjVex[x].append(y)\n",
    "            adjVex[y].append(x)\n",
    "\n",
    "        que = [0]\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        visited[0] = True\n",
    "        cur = 0\n",
    "        while que:\n",
    "            cur_len = len(que)\n",
    "            for _ in range(cur_len):\n",
    "                cur = que.pop(0)\n",
    "                for nxt in adjVex[cur]:\n",
    "                    if visited[nxt] == False:\n",
    "                        visited[nxt] = True\n",
    "                        que.append(nxt)\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        que = [cur]\n",
    "        visited[cur] = True \n",
    "        level = -1\n",
    "        while que:\n",
    "            cur_len = len(que)\n",
    "            level += 1\n",
    "            for _ in range(cur_len):\n",
    "                cur = que.pop(0)\n",
    "                for nxt in adjVex[cur]:\n",
    "                    if visited[nxt] == False:\n",
    "                        visited[nxt] = True \n",
    "                        que.append(nxt)\n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        adjVex = defaultdict(list)  #邻接表\n",
    "        for x, y in edges:          #初始化邻接表，建图\n",
    "            adjVex[x].append(y)\n",
    "            adjVex[y].append(x)\n",
    "        \n",
    "        que = [0]\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        visited[0] = True\n",
    "        cur = 0                     #全局变量，好记录第一次BFS最后一个点的ID\n",
    "        while que:\n",
    "            cur_len = len(que)\n",
    "            for _ in range(cur_len):\n",
    "                cur = que.pop(0)\n",
    "                for nxt in adjVex[cur]:\n",
    "                    if visited[nxt] == False:\n",
    "                        visited[nxt] = True #进队时visit和出队时visit都可以\n",
    "                        que.append(nxt)\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        que = [cur]                         #第一次最后一个点，作为第二次BFS的起点\n",
    "        visited[cur] = True\n",
    "        level = -1                          #记好距离\n",
    "        while que:\n",
    "            cur_len = len(que)\n",
    "            level += 1\n",
    "            for _ in range(cur_len):\n",
    "                cur = que.pop(0)\n",
    "                for nxt in adjVex[cur]:\n",
    "                    if visited[nxt] == False:\n",
    "                        visited[nxt] = True\n",
    "                        que.append(nxt)\n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if len(edges) == 0:\n",
    "            return 0\n",
    "            \n",
    "        self.res = 0 \n",
    "\n",
    "        self.visited = set([])\n",
    "\n",
    "        self.tree = defaultdict(list)\n",
    "\n",
    "        for a, b in edges:\n",
    "            self.tree[a].append(b)\n",
    "            self.tree[b].append(a)\n",
    "\n",
    "        root = self.tree[0][0]\n",
    "\n",
    "        self.getDiameter(root)\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def getDiameter(self, root):\n",
    "        if root in self.visited:\n",
    "            return 0\n",
    "\n",
    "        self.visited.add(root)\n",
    "\n",
    "        max1, max2 = 0, 0\n",
    "        for child in self.tree[root]:\n",
    "            child_diameter = self.getDiameter(child)\n",
    "\n",
    "            if child_diameter >= max1:\n",
    "                max2 = max1\n",
    "                max1 = child_diameter\n",
    "            elif child_diameter > max2:\n",
    "                max2 = child_diameter \n",
    "\n",
    "        diameter = max1 + max2\n",
    "\n",
    "        self.res = max(self.res, diameter)\n",
    "\n",
    "        return 1 + max1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        graph = collections.defaultdict(list)\n",
    "        degree = [0] * n\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "            degree[edge[0]] += 1\n",
    "            degree[edge[1]] += 1\n",
    "        q = [u for u in range(n) if degree[u] == 1]\n",
    "        left_node = n\n",
    "        res = 0\n",
    "        while left_node > 1:\n",
    "            level = len(q)\n",
    "            for _ in range(level):\n",
    "                u = q.pop(0)\n",
    "                for v in graph[u]:\n",
    "                    degree[v] -= 1\n",
    "                    if degree[v] == 1:\n",
    "                        q.append(v)\n",
    "            res += 2\n",
    "            left_node -= level\n",
    "        if left_node == 0:\n",
    "            res -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        graph = collections.defaultdict(list)\n",
    "        degree = [0] * n\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "            degree[edge[0]] += 1\n",
    "            degree[edge[1]] += 1\n",
    "        q = [u for u in range(n) if degree[u] == 1]\n",
    "        left_node = n\n",
    "        res = 0\n",
    "        while left_node > 1:\n",
    "            level = len(q)\n",
    "            for _ in range(level):\n",
    "                u = q.pop(0)\n",
    "                for v in graph[u]:\n",
    "                    degree[v] -= 1\n",
    "                    if degree[v] == 1:\n",
    "                        q.append(v)\n",
    "            left_node -= level\n",
    "            res += 2\n",
    "        return res if left_node == 1 else res - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if len(edges)<=2:return len(edges)\n",
    "        g=collections.defaultdict(list)\n",
    "        count=collections.Counter()\n",
    "        for i,j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "            count[i]+=1\n",
    "            count[j]+=1\n",
    "        m=len(edges)+1\n",
    "        queue=[i for i in range(m) if count[i]==1]\n",
    "        queue=deque(queue)\n",
    "        n=0\n",
    "        while queue and m>2:\n",
    "            size=len(queue)\n",
    "            for _ in range(size):\n",
    "                x=queue.popleft()\n",
    "                for i in g[x]:\n",
    "                    count[i]-=1\n",
    "                    if count[i]==1:\n",
    "                        queue.append(i)\n",
    "            n+=1\n",
    "            m-=size\n",
    "        return n*2+m//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if len(edges)<=2:\n",
    "            return len(edges)\n",
    "        u=collections.defaultdict(list)\n",
    "        count=collections.Counter()\n",
    "        for i,j in edges:\n",
    "            u[i].append(j)\n",
    "            u[j].append(i)\n",
    "            count[i]+=1\n",
    "            count[j]+=1\n",
    "\n",
    "        queue=deque([i for i in count if count[i]==1])\n",
    "        n=len(edges)+1\n",
    "        ans=0\n",
    "        while n>2:\n",
    "            size=len(queue)\n",
    "            n=n-size\n",
    "            for _ in range(size):\n",
    "                x=queue.popleft()\n",
    "                for key in u[x]:\n",
    "                    count[key]-=1\n",
    "                    if count[key]==1:\n",
    "                        queue.append(key)\n",
    "            ans+=2\n",
    "        return ans+1 if n==2 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if not edges:\n",
    "            return 0\n",
    "        n=len(edges)+1\n",
    "        e=collections.defaultdict(list)\n",
    "        d=[0]*n\n",
    "        for a,b in edges:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "            d[a]+=1\n",
    "            d[b]+=1\n",
    "        q=collections.deque()\n",
    "        for i in range(n):\n",
    "            if d[i]==1:\n",
    "                q.append(i)\n",
    "        loop=0\n",
    "        n=0\n",
    "        while q:\n",
    "            n=len(q)\n",
    "            print(n)\n",
    "            for i in range(n):\n",
    "                tp=q.popleft()\n",
    "                for j in e[tp]:\n",
    "                    d[j]-=1\n",
    "                    if d[j]==1:\n",
    "                        q.append(j)\n",
    "            loop+=1\n",
    "        print(loop)\n",
    "        ret=loop*2\n",
    "        if n==1:\n",
    "            ret-=1\n",
    "        return ret-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if len(edges)<=2:return len(edges)\n",
    "        g=collections.defaultdict(list)\n",
    "        count=collections.Counter()\n",
    "        for i,j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "            count[i]+=1\n",
    "            count[j]+=1\n",
    "        m=len(edges)+1\n",
    "        queue=[i for i in range(m) if count[i]==1]\n",
    "        queue=deque(queue)\n",
    "        n=0\n",
    "        while queue and m>2:\n",
    "            size=len(queue)\n",
    "            for _ in range(size):\n",
    "                x=queue.popleft()\n",
    "                for i in g[x]:\n",
    "                    count[i]-=1\n",
    "                    if count[i]==1:\n",
    "                        queue.append(i)\n",
    "            n+=1\n",
    "            m-=size\n",
    "        return n*2+m//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        #树形DP\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n+1)]\n",
    "        graph[0].append(-1)\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        ans=0\n",
    "        def dfs(x,fa):\n",
    "            nonlocal ans\n",
    "            if len(graph[x])==1:\n",
    "                return 1\n",
    "            cur=0\n",
    "            dp=[0,0]\n",
    "            for y in graph[x]:\n",
    "                if y==fa: continue\n",
    "                nex=dfs(y,x)\n",
    "                cur=max(cur,nex)\n",
    "                if nex>dp[1]:\n",
    "                    dp[0]=dp[1]\n",
    "                    dp[1]=nex\n",
    "                elif nex>dp[0]:\n",
    "                    dp[0]=nex\n",
    "            ans=max(ans,dp[0]+dp[1])\n",
    "            return cur+1\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        # 0 <= edges.length < 10^4\n",
    "        # 这是一个无向树，意味着不存在环\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        # 随便从一个结点出发计算得到的结果都是一样的\n",
    "        # 这个其实难在多叉树需要用堆来维护一下而已\n",
    "        def dfs(x, fa):\n",
    "            h = []\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    v = dfs(y, x)\n",
    "                    heappush(h, -v)\n",
    "            ret = 0\n",
    "            ans = 0\n",
    "            for _ in range(2):\n",
    "                if h: \n",
    "                    v = -heappop(h)\n",
    "                    ret = max(ret, 1+v) \n",
    "                    ans += 1 + v   \n",
    "            nonlocal ma\n",
    "            ma = max(ma, ans)\n",
    "            return ret\n",
    "        \n",
    "        ma = 0\n",
    "        dfs(0, -1)\n",
    "        return ma\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        #树形DP\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n+1)]\n",
    "        graph[0].append(-1)\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        ans=0\n",
    "        def dfs(x,fa):\n",
    "            nonlocal ans\n",
    "            if len(graph[x])==1:\n",
    "                return 1\n",
    "            #巧妙迭代,求子树中距离最大的两条路径之和\n",
    "            max_len=0\n",
    "            for y in graph[x]:\n",
    "                if y==fa: continue\n",
    "                nex=dfs(y,x)\n",
    "                ans=max(ans,nex+max_len)\n",
    "                max_len=max(max_len,nex)\n",
    "            return max_len+1\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n+1)]\n",
    "        graph[0].append(-1)\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        ans=0\n",
    "        def dfs(x,fa):\n",
    "            nonlocal ans\n",
    "            if len(graph[x])==1:\n",
    "                return 1\n",
    "            cur=0\n",
    "            dp=[0,0]\n",
    "            for y in graph[x]:\n",
    "                if y==fa: continue\n",
    "                nex=dfs(y,x)\n",
    "                cur=max(cur,nex)\n",
    "                if nex>dp[1]:\n",
    "                    dp[0]=dp[1]\n",
    "                    dp[1]=nex\n",
    "                elif nex>dp[0]:\n",
    "                    dp[0]=nex\n",
    "            ans=max(ans,dp[0]+dp[1])\n",
    "            return cur+1\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        # MX = 0\n",
    "        # for a,b in edges:\n",
    "        #     MX = max(a,b,MX)\n",
    "        # n条边，n+1个节点\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(i,fa):\n",
    "            nonlocal ans\n",
    "            a = b = 0\n",
    "            for j in g[i]:\n",
    "                if j == fa:continue\n",
    "                t = dfs(j,i)\n",
    "                if t > a:\n",
    "                    b =a \n",
    "                    a = t\n",
    "                elif t>b:\n",
    "                    b = t\n",
    "            ans = max(ans, a+b+1)\n",
    "            return a + 1\n",
    "        dfs(0,-1)\n",
    "        return ans-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        MX = 10**4+1\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(i,fa):\n",
    "            nonlocal ans\n",
    "            a = b = 0\n",
    "            for j in g[i]:\n",
    "                if j == fa:continue\n",
    "                t = dfs(j,i)\n",
    "                if t > a:\n",
    "                    b =a \n",
    "                    a = t\n",
    "                elif t>b:\n",
    "                    b = t\n",
    "            ans = max(ans, a+b+1)\n",
    "            return a + 1\n",
    "        dfs(0,-1)\n",
    "        return ans-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        # MX = 0\n",
    "        # for a,b in edges:\n",
    "        #     MX = max(a,b,MX)\n",
    "        # n条边，n+1个节点\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(i,fa):\n",
    "            nonlocal ans\n",
    "            a = b = 0\n",
    "            for j in g[i]:\n",
    "                if j == fa:continue\n",
    "                t = dfs(j,i)\n",
    "                if t > a:\n",
    "                    b =a \n",
    "                    a = t\n",
    "                elif t>b:\n",
    "                    b = t\n",
    "            ans = max(ans, a+b+1)\n",
    "            return a + 1\n",
    "        dfs(0,-1)\n",
    "        return ans-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        #树形DP\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n+1)]\n",
    "        graph[0].append(-1)\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        ans=0\n",
    "        def dfs(x,fa):\n",
    "            nonlocal ans\n",
    "            if len(graph[x])==1:\n",
    "                return 1\n",
    "            cur=0\n",
    "            dp=[0,0]\n",
    "            for y in graph[x]:\n",
    "                if y==fa: continue\n",
    "                nex=dfs(y,x)\n",
    "                cur=max(cur,nex)\n",
    "                if nex>dp[1]:\n",
    "                    dp[0]=dp[1]\n",
    "                    dp[1]=nex\n",
    "                elif nex>dp[0]:\n",
    "                    dp[0]=nex\n",
    "            ans=max(ans,dp[0]+dp[1])\n",
    "            return cur+1\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        \n",
    "        if not edges or len(edges) == 0:\n",
    "            return 0\n",
    "        n = len(edges)\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        ans = 0\n",
    "        def dfs(u,fa):\n",
    "            x_len = 0\n",
    "            nonlocal ans\n",
    "            for y in g[u]:\n",
    "                if fa == y:\n",
    "                    continue\n",
    "                y_len = dfs(y,u)+1\n",
    "                ans = max(x_len+y_len,ans) \n",
    "                x_len = max(x_len,y_len)\n",
    "            return x_len\n",
    "        dfs(edges[0][0],-1)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        n = 0\n",
    "        for x, y in edges:\n",
    "            n = max(n, max(x, y))\n",
    "        n += 1\n",
    "        dp = [0 for _ in range(n)]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfs(now, fa, ans):\n",
    "            reslist = []\n",
    "            for nxt in g[now]:\n",
    "                if nxt == fa:\n",
    "                    continue\n",
    "                ans = max(ans, dfs(nxt, now, ans))\n",
    "                reslist.append(dp[nxt])\n",
    "            if len(reslist) > 0:\n",
    "                reslist.sort(reverse=True)\n",
    "                dp[now] = max(dp[now], reslist[0]+1)\n",
    "                if len(reslist) > 1:\n",
    "                    ans = max(ans, reslist[0] + reslist[1] + 2)\n",
    "            return max(ans, dp[now])\n",
    "        return dfs(0, -1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        #树形DP\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n+1)]\n",
    "        graph[0].append(-1)\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        ans=0\n",
    "        def dfs(x,fa):\n",
    "            nonlocal ans\n",
    "            if len(graph[x])==1:\n",
    "                return 1\n",
    "            #巧妙迭代,求子树中距离最大的两条路径之和\n",
    "            max_len=0\n",
    "            for y in graph[x]:\n",
    "                if y==fa: continue\n",
    "                nex=dfs(y,x)\n",
    "                ans=max(ans,nex+max_len)\n",
    "                max_len=max(max_len,nex)\n",
    "            return max_len+1\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        if n==1: return 0\n",
    "        self.res = 0\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        def dfs(x,fa):\n",
    "            # 每个节点有往下的最大值down，以及curve\n",
    "            # down 是可传递的\n",
    "            if len(g[x])==1 and g[x][0] == fa:\n",
    "                return 1\n",
    "            down_list = []\n",
    "            for y in g[x]:\n",
    "                if y!=fa:\n",
    "                    heapq.heappush(down_list, -dfs(y,x))\n",
    "            cur_down = 1 - heapq.heappop(down_list)\n",
    "            curve = cur_down\n",
    "            if down_list:\n",
    "                curve -= heapq.heappop(down_list)\n",
    "            self.res = max(self.res, curve, cur_down)\n",
    "            return cur_down\n",
    "        dfs(0,-1)\n",
    "        return self.res - 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxDiameter = 0\n",
    "        self.tree =  collections.defaultdict(list)\n",
    "        self.visited = set()\n",
    "        self.depth = collections.defaultdict(int)\n",
    "\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if len(edges) == 0:\n",
    "            return 0\n",
    "        for edge in edges:  #多叉树的记录表现形式\n",
    "            a, b = edge[0], edge[1]\n",
    "            self.tree[a].append(b)\n",
    "            self.tree[b].append(a)\n",
    "\n",
    "        self.maxDepth(edges[0][0])\n",
    "        return self.maxDiameter\n",
    "\n",
    "    def maxDepth(self, root: int) -> int:\n",
    "        if root in self.visited:\n",
    "            return 0\n",
    "        self.visited.add(root)\n",
    "\n",
    "        firstMaxDepth, secondMaxDepth = 0, 0  #记录第一第二的要记住\n",
    "\n",
    "        for child in self.tree[root]:\n",
    "            if child in self.depth:\n",
    "                chlidDepth = self.depth[child]\n",
    "            else:\n",
    "                chlidDepth = self.maxDepth(child)\n",
    "            if chlidDepth >= firstMaxDepth:\n",
    "                secondMaxDepth = firstMaxDepth\n",
    "                firstMaxDepth = chlidDepth\n",
    "            elif chlidDepth > secondMaxDepth:\n",
    "                secondMaxDepth = chlidDepth\n",
    "\n",
    "        myDiameter = firstMaxDepth + secondMaxDepth\n",
    "        self.maxDiameter = max(self.maxDiameter, myDiameter)\n",
    "        self.depth[root] = 1 + firstMaxDepth\n",
    "\n",
    "        return 1 + firstMaxDepth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list) \n",
    "        for a, b in edges:\n",
    "            g[a].append(b) \n",
    "            g[b].append(a) \n",
    "        mx, x = 0, 0 \n",
    "        def dfs(u, d, fa):\n",
    "            nonlocal mx, x \n",
    "            if d > mx:\n",
    "                mx = d \n",
    "                x = u \n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    dfs(v,d+1,u) \n",
    "        dfs(0, 0, 0)\n",
    "        mx = 0 \n",
    "        dfs(x, 0, x) \n",
    "        return mx "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        self.res = 0\n",
    "        # returns the longest path starting from node\n",
    "        def dfs(node, fa):\n",
    "            max1, max2 = 0, 0\n",
    "            for adj in graph[node]:\n",
    "                if adj == fa: continue\n",
    "                tmp = dfs(adj, node) + 1\n",
    "                if tmp > max1:\n",
    "                    max2 = max1\n",
    "                    max1 = tmp\n",
    "                elif tmp > max2:\n",
    "                    max2 = tmp\n",
    "            self.res = max(self.res, max1 + max2)\n",
    "            return max1\n",
    "        dfs(0, -1)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        # 一个节点的最长边和第二长边\n",
    "        \n",
    "        ans = 0\n",
    "        def dfs(node, fa):\n",
    "            nonlocal ans\n",
    "            top1 = top2 = 0\n",
    "            for son in graph[node]:\n",
    "                if son != fa:\n",
    "                    dis = 1 + dfs(son, node)\n",
    "                    _, top2, top1 = sorted((dis, top1, top2))\n",
    "                    ans = max(ans, top1 + top2)\n",
    "            return top1\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        self.res = 0\n",
    "        def dfs(x, parent):\n",
    "            x_len = 0\n",
    "            for y in g[x]:\n",
    "                if y == parent:\n",
    "                    continue\n",
    "                y_len = dfs(y, x) + 1\n",
    "                self.res = max(self.res, x_len + y_len)\n",
    "                x_len = max(x_len, y_len)\n",
    "            return x_len\n",
    "        dfs(0, -1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        ans = 0\n",
    "        def DFS(x, parent):\n",
    "            nonlocal ans \n",
    "\n",
    "            max_s = 0 \n",
    "            for y in graph[x]:\n",
    "                if y== parent:\n",
    "                    continue \n",
    "\n",
    "                child_s = DFS(y,x)\n",
    "                ans = max(ans, max_s+child_s+1)\n",
    "\n",
    "                max_s = max(max_s, child_s+1)\n",
    "            \n",
    "            return max_s\n",
    "        DFS(0,-1)\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        self.res = 0\n",
    "        def dfs(x, parent): # dfs(0), x = 0, parent = -1, dfs(1, 0)\n",
    "            first = 0\n",
    "            for y in g[x]:\n",
    "                if y == parent:\n",
    "                    continue\n",
    "                second = dfs(y, x) + 1\n",
    "                self.res = max(self.res, first + second)\n",
    "                first = max(first, second)\n",
    "            return first\n",
    "        dfs(0, -1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if not edges:\n",
    "            return 0\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        self.ans = 0\n",
    "        def dfs(u,fa):    \n",
    "            maxv = 0\n",
    "            for v in g[u]:\n",
    "                if v == fa:\n",
    "                    continue\n",
    "                cur = dfs(v,u)    \n",
    "                self.ans = max(self.ans, maxv + cur+1)\n",
    "                maxv = max(maxv,cur)\n",
    "            return maxv + 1\n",
    "        dfs(edges[0][0], -1)\n",
    "        return self.ans -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        # construct graph\n",
    "        graph = defaultdict(list)\n",
    "        for a, b in edges: \n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        def dfs(root, parent, distance): \n",
    "            farest_node = (distance, root)\n",
    "            for neighbor in graph[root]: \n",
    "                if neighbor == parent: \n",
    "                    continue # Tree到达叶节点的检查方法\n",
    "                farest_node = max(farest_node, dfs(neighbor, root, distance + 1))\n",
    "            return farest_node\n",
    "        \n",
    "        # run dfs on any node to get the farest node from this node\n",
    "        _, a = dfs(0, None, 0)\n",
    "        # run dfs from this node, get the diameter\n",
    "        diameter, _ = dfs(a, None, 0)\n",
    "        return diameter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        dic=defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            dic[i].append(j)\n",
    "            dic[j].append(i)\n",
    "        \n",
    "        ans=0\n",
    "        def dfs(x,fa):\n",
    "            nonlocal ans\n",
    "            cur=0\n",
    "            for nxt in dic[x]:\n",
    "                if nxt==fa:\n",
    "                    continue\n",
    "                l=dfs(nxt,x)\n",
    "                ans=max(ans,cur+l)\n",
    "                cur=max(cur,l)\n",
    "            return cur+1\n",
    "        dfs(0,-1)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(u,fa):\n",
    "            mx = 0\n",
    "            nonlocal ans\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    t = dfs(v,u) + 1\n",
    "                    ans = max(ans,t + mx)\n",
    "                    mx = max(mx,t)\n",
    "            return mx\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        g = defaultdict(list) \n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        res = 0\n",
    "        def dfs(root, fa):\n",
    "            nonlocal res\n",
    "            max_1, max_2 = 0, 0 # 表示经过该节点，最长的两个分支\n",
    "            for nxt in g[root]:\n",
    "                if nxt != fa:\n",
    "                    max_2 = 1 + dfs(nxt, root)\n",
    "                    res = max(res, max_1 + max_2)\n",
    "                    max_1 = max(max_1, max_2)\n",
    "            return max_1 # 返回上去的是这个节点经过的最长的分支\n",
    "        dfs(0, -1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if edges == []:\n",
    "            return 0\n",
    "        tree = collections.defaultdict(list)\n",
    "        for fr, to in edges:\n",
    "            tree[fr].append(to)\n",
    "            tree[to].append(fr)\n",
    "        visited = []\n",
    "        res = 0\n",
    "        def dfs(root):\n",
    "            firstMaxDepth, secondMaxDepth = 0, 0\n",
    "            nonlocal res, visited\n",
    "            if root in visited: return 0\n",
    "            visited.append(root)\n",
    "            for child in tree[root]:\n",
    "                chlidDepth = dfs(child)\n",
    "                if chlidDepth >= firstMaxDepth:\n",
    "                    secondMaxDepth = firstMaxDepth\n",
    "                    firstMaxDepth = chlidDepth\n",
    "                elif chlidDepth > secondMaxDepth:\n",
    "                    secondMaxDepth = chlidDepth\n",
    "            rootmax = firstMaxDepth + secondMaxDepth\n",
    "            res = max(res, rootmax)\n",
    "            return 1 + firstMaxDepth\n",
    "\n",
    "        dfs(edges[0][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#python版本树形DP\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if not edges:\n",
    "            return 0\n",
    "        adj=defaultdict(list)\n",
    "        for node1,node2 in edges:\n",
    "            adj[node1].append(node2)\n",
    "            adj[node2].append(node1)\n",
    "        \n",
    "        res=0\n",
    "        n=len(adj)\n",
    "        visited=[0]*n\n",
    "\n",
    "        def dfs(node): # 返回值是以node为根节点的树中，最大链长\n",
    "            nonlocal res\n",
    "            x_len=0\n",
    "            for children in adj[node]:\n",
    "                if visited[children]:\n",
    "                    continue\n",
    "                visited[children]=1\n",
    "                y_len=dfs(children)+1\n",
    "                res=max(res,x_len+y_len)\n",
    "                x_len=max(x_len,y_len)\n",
    "            return x_len\n",
    "\n",
    "        \n",
    "        visited[0]=1\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#python版本树形DP\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if not edges:\n",
    "            return 0\n",
    "        adj=defaultdict(list)\n",
    "        for node1,node2 in edges:\n",
    "            adj[node1].append(node2)\n",
    "            adj[node2].append(node1)\n",
    "        \n",
    "        res=0\n",
    "        n=len(adj)\n",
    "        visited=[0]*n\n",
    "\n",
    "        def dfs(node): # 返回值是以node为根节点的树中，最大链长\n",
    "            nonlocal res\n",
    "            x_len=0\n",
    "            for children in adj[node]:\n",
    "                if visited[children]:\n",
    "                    continue\n",
    "                visited[children]=1\n",
    "                y_len=dfs(children)+1\n",
    "                res=max(res,x_len+y_len)\n",
    "                x_len=max(x_len,y_len)\n",
    "            return x_len\n",
    "\n",
    "        \n",
    "        visited[0]=1\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        graph = [set() for i in range(n+1)]\n",
    "\n",
    "        for edge in edges:\n",
    "            u,v = edge\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        \n",
    "        def bfs(node_idx) -> (int, int):\n",
    "            visited = [False] * len(graph)\n",
    "            visited[node_idx] = True\n",
    "            queue = deque([node_idx])\n",
    "            distance = -1\n",
    "            last_node = None\n",
    "            while queue:\n",
    "                next_q = deque()\n",
    "                while queue:\n",
    "                    next_node = queue.popleft()\n",
    "                    for neig in graph[next_node]:\n",
    "                        if not visited[neig]:\n",
    "                            visited[neig] = True\n",
    "                            next_q.append(neig)\n",
    "                            last_node = neig\n",
    "                distance += 1\n",
    "                queue = next_q\n",
    "            return last_node, distance\n",
    "        \n",
    "        farthest_node, distance_1 = bfs(0)\n",
    "        another_node, ans = bfs(farthest_node)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        # get all nodes \n",
    "        nodes = set()\n",
    "        for u, v in edges:\n",
    "            if u not in nodes:\n",
    "                nodes.add(u)\n",
    "            if v not in nodes:\n",
    "                nodes.add(v)\n",
    "        # print(nodes)\n",
    "\n",
    "        #store node x's childs \n",
    "        g = {} # 1: 0,2,4 store parent node and its childs \n",
    "        for x, y in edges:\n",
    "            if x not in g:\n",
    "                g[x] = [y]\n",
    "            else:\n",
    "                g[x].append(y)\n",
    "        # {0:[1,2]}\n",
    "\n",
    "        for node in nodes:\n",
    "            if node in g: continue\n",
    "            else: \n",
    "                g[node] = []\n",
    "        \n",
    "        #print(g)\n",
    "        if edges == []: return 0\n",
    "\n",
    "        ans  = 0 \n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            maxLen = 0 \n",
    "            for y in g[x]:\n",
    "                currentLen = dfs(y) +1 \n",
    "                ans = max(ans, maxLen+currentLen)\n",
    "                maxLen = max(currentLen, maxLen)\n",
    "            \n",
    "            return maxLen \n",
    "        \n",
    "        dfs(edges[0][0])\n",
    "\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        # get all nodes \n",
    "        nodes = set()\n",
    "        for u, v in edges:\n",
    "            if u not in nodes:\n",
    "                nodes.add(u)\n",
    "            if v not in nodes:\n",
    "                nodes.add(v)\n",
    "        # print(nodes)\n",
    "\n",
    "        #store node x's childs \n",
    "        g = {} # 1: 0,2,4 store parent node and its childs \n",
    "        for x, y in edges:\n",
    "            if x not in g:\n",
    "                g[x] = [y]\n",
    "            else:\n",
    "                g[x].append(y)\n",
    "        # {0:[1,2]}\n",
    "\n",
    "        for node in nodes:\n",
    "            if node in g: continue\n",
    "            else: \n",
    "                g[node] = []\n",
    "        \n",
    "        #print(g)\n",
    "        if edges == []: return 0\n",
    "\n",
    "        ans  = 0 \n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            maxLen = 0 \n",
    "            for y in g[x]:\n",
    "                currentLen = dfs(y) +1 \n",
    "                ans = max(ans, maxLen+currentLen)\n",
    "                maxLen = max(currentLen, maxLen)\n",
    "            \n",
    "            return maxLen \n",
    "        \n",
    "        dfs(edges[0][0])\n",
    "\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        # 深度优先搜索\n",
    "        def dfs(node, visited):\n",
    "            visited.add(node)\n",
    "            max_distance1, max_distance2 = 0, 0\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    d = dfs(neighbor, visited)\n",
    "                    if d > max_distance1:\n",
    "                        max_distance1, max_distance2 = d, max_distance1\n",
    "                    elif d > max_distance2:\n",
    "                        max_distance2 = d\n",
    "            self.result = max(self.result, max_distance1 + max_distance2)\n",
    "            return 1 + max_distance1\n",
    "\n",
    "        self.result = 0\n",
    "        dfs(0, set())\n",
    "        return self.result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        graph = defaultdict(list)\n",
    "        root = None\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "            if root is None:\n",
    "                root = min(x, y)\n",
    "            else:\n",
    "                root = min([root, x, y])\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal result\n",
    "            max_dis1, max_dis2 = 0, 0\n",
    "            visited.add(root)\n",
    "            for neighber in graph[root]:\n",
    "                if neighber in visited:\n",
    "                    continue\n",
    "                dis = 1 + dfs(neighber)\n",
    "                if dis > max_dis1:\n",
    "                    max_dis2 = max_dis1\n",
    "                    max_dis1 = dis\n",
    "                elif dis > max_dis2:\n",
    "                    max_dis2 = dis\n",
    "            result = max(result, max_dis1 + max_dis2)\n",
    "            return max_dis1\n",
    "\n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        graph = defaultdict(list)\n",
    "        root = None\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "            if root is None:\n",
    "                root = min(x, y)\n",
    "            else:\n",
    "                root = min([root, x, y])\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal result\n",
    "            max_dis1, max_dis2 = 0, 0\n",
    "            visited.add(root)\n",
    "            for neighber in graph[root]:\n",
    "                if neighber in visited:\n",
    "                    continue\n",
    "                dis = 1 + dfs(neighber)\n",
    "                if dis > max_dis1:\n",
    "                    max_dis2 = max_dis1\n",
    "                    max_dis1 = dis\n",
    "                elif dis > max_dis2:\n",
    "                    max_dis2 = dis\n",
    "            result = max(result, max_dis1 + max_dis2)\n",
    "            return max_dis1\n",
    "\n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        \n",
    "        for e1, e2 in edges:\n",
    "            graph[e1].append(e2)\n",
    "            graph[e2].append(e1)\n",
    "        \n",
    "        res = 0\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            if not graph[node]:\n",
    "                return\n",
    "\n",
    "            visited.add(node)\n",
    "\n",
    "            temp1, temp2 = 0,0\n",
    "            for cur in graph[node]:\n",
    "                if cur not in visited:\n",
    "                    num = dfs(cur)\n",
    "                    temp1, temp2 = max(temp1, num), min(temp1, max(num, temp2))\n",
    "\n",
    "            nonlocal res\n",
    "            res = max(res, temp1 + temp2)\n",
    "            return max(temp1, temp2) + 1\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        vis = set()\n",
    "        def get_height_and_diameter(root):\n",
    "            vis.add(root)\n",
    "            top_sub_heights = [-1, -1]\n",
    "            sub_diameters = []\n",
    "            for child in graph[root]:\n",
    "                if child not in vis:\n",
    "                    sub_height, sub_diameter = get_height_and_diameter(child)\n",
    "                    top_sub_heights.append(sub_height)\n",
    "                    if sub_diameter == sub_height:   # root is 1 end of the diameter\n",
    "                        sub_diameters.append(sub_diameter + 1)\n",
    "                    else:\n",
    "                        sub_diameters.append(sub_diameter)\n",
    "            top_sub_heights.sort(reverse=True)\n",
    "            sub_diameters.append(top_sub_heights[0] + top_sub_heights[1] + 2)\n",
    "            return top_sub_heights[0] + 1, max(sub_diameters)\n",
    "        height, diameter = get_height_and_diameter(0)\n",
    "        return diameter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        if edges == []:\n",
    "            return 0\n",
    "        path = dict()\n",
    "        for x, y in edges:\n",
    "            if x not in path:\n",
    "                path[x] = {y}\n",
    "            else:\n",
    "                path[x].add(y)\n",
    "            if y not in path:\n",
    "                path[y] = {x}\n",
    "            else:\n",
    "                path[y].add(x)\n",
    "        def cnt():\n",
    "            if len(path) <= 3: return len(path) - 1\n",
    "            node = []\n",
    "            for x in path:\n",
    "                if len(path[x]) == 1:\n",
    "                    node.append(x)\n",
    "            for k in node:\n",
    "                cur = path.pop(k)\n",
    "                cur = list(cur)[0]\n",
    "                path[cur].remove(k)\n",
    "            return 2 + cnt()\n",
    "        return cnt()\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        vis = set()\n",
    "        def get_height_and_diameter(root):\n",
    "            vis.add(root)\n",
    "            top_sub_heights = [-1, -1]\n",
    "            sub_diameters = []\n",
    "            for child in graph[root]:\n",
    "                if child not in vis:\n",
    "                    sub_height, sub_diameter = get_height_and_diameter(child)\n",
    "                    top_sub_heights.append(sub_height)\n",
    "                    if sub_diameter == sub_height:   # root is 1 end of the diameter\n",
    "                        sub_diameters.append(sub_diameter + 1)\n",
    "                    else:\n",
    "                        sub_diameters.append(sub_diameter)\n",
    "            top_sub_heights.sort(reverse=True)\n",
    "            sub_diameters.append(top_sub_heights[0] + top_sub_heights[1] + 2)\n",
    "            return top_sub_heights[0] + 1, max(sub_diameters)\n",
    "        height, diameter = get_height_and_diameter(0)\n",
    "        return diameter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeDiameter(self, edges: List[List[int]]) -> int:\n",
    "        #Build Graph\n",
    "        graph = collections.defaultdict(list)\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "        \n",
    "        end_node = None\n",
    "        dis = 0\n",
    "        visited = set()\n",
    "        def dfs(node, cur):\n",
    "            nonlocal dis\n",
    "            nonlocal end_node\n",
    "            visited.add(node)\n",
    "            end = True\n",
    "            for child in graph[node]:\n",
    "                if child not in visited:\n",
    "                    end = False\n",
    "                    dfs(child, cur + 1)\n",
    "            if end == True:\n",
    "                if cur > dis:\n",
    "                    dis = cur\n",
    "                    end_node = node\n",
    "        \n",
    "        dfs(0, 0)\n",
    "\n",
    "        dis = 0\n",
    "        visited = set()\n",
    "        dfs(end_node, 0)\n",
    "\n",
    "        return dis"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
